// https://www.lintcode.com/problem/longest-palindromic-subsequence/my-submissions

class Solution {
public:
    /**
     * @param s: the maximum length of s is 1000
     * @return: the longest palindromic subsequence's length
     */
    
    // 区间型dp标准
    // int longestPalindromeSubseq(string &s) {
    //     int n = s.length();
    //     // if (n == 0) return 0;
    //     if (n <= 1) return n;
    //     vector<vector<int>> res(n, vector<int>(n, 1));
    //     for (int i = 0; i < n - 1; ++i)
    //     {
    //         if (s[i] == s[i + 1])
    //             res[i][i + 1] = 2;
    //     }
    //     for (int len = 2; len < n; ++len)
    //     {
    //         for (int i = 0; i < n - len; ++i)
    //         {
    //             if (s[i] == s[i + len])
    //                 res[i][i + len] = res[i + 1][i + len - 1] + 2;
    //             res[i][i + len] = max(res[i][i + len], max(res[i + 1][i + len], res[i][i + len - 1]));
    //         } 
    //     }
    //     return res[0][n - 1];
    // }
    
    // 答案
    // int longestPalindromeSubseq(string& s) {
    //     // Write your code here
    //     int length = s.size();
    //     if (length == 0)
    //         return 0;
    //     vector<vector<int>> dp(length, vector<int>(length));
    //     for (int i = length - 1; i >= 0; i--) {
    //         dp[i][i] = 1;
    //         for (int j = i + 1; j < length; j++) {
    //             if (s[i] == s[j]) {
    //                 dp[i][j] = dp[i + 1][j - 1] + 2;
    //             } else {
    //                 dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]);
    //             }
    //         }
    //     }
    //     return dp[0][length - 1];
    // }
    
    
    // 记忆化搜索标准
    void calc(int i, int j, vector<vector<int>> &f, string &s)
    {
        if (f[i][j] != -1) //核心
            return;
        
        if (i == j){
            f[i][j] = 1; //别忘了
            return;
        }
        if (j == i + 1)
        {
            f[i][j] = (s[i] == s[j]) ? 2: 1;
            return;
        }
        calc(i + 1, j, f, s);
        calc(i, j - 1, f, s);
        calc(i + 1, j - 1, f, s);
        
        if (s[i] == s[j])
            f[i][j] = f[i + 1][j - 1] + 2;
        f[i][j] = max(f[i][j], max(f[i][j - 1], f[i + 1][j]));
    }
    int longestPalindromeSubseq(string &s) {
        int n = s.length();
        if (n <= 1)
            return n;
        vector<vector<int>> rec(n, vector<int>(n, -1));
        calc(0, n - 1, rec, s);
        return rec[0][n - 1];
    }
};